home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / CH_6.1 / XVOR / EDGELIST.C next >
C/C++ Source or Header  |  1999-09-11  |  4KB  |  190 lines
  1. /* 
  2.  * edgelist.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9. /*
  10.  * EDGELIST 
  11.  *
  12.  */
  13. #include <stdlib.h>
  14. #include "vor.h"
  15.  
  16. int ntry, totalsearch;
  17.  
  18. void
  19. ELinitialize ()
  20. {
  21.   int i;
  22.  
  23.   freeinit (&hfl, sizeof **ELhash);
  24.  
  25.   ELhashsize = 2 * sqrt_nsites;
  26.   ELhash = (struct Halfedge **) myalloc (sizeof *ELhash * ELhashsize);
  27.  
  28.   for (i = 0; i < ELhashsize; i += 1)
  29.     ELhash[i] = (struct Halfedge *) NULL;
  30.  
  31.   ELleftend = HEcreate ((struct Edge *) NULL, 0);
  32.   ELrightend = HEcreate ((struct Edge *) NULL, 0);
  33.  
  34.   ELleftend->ELleft = (struct Halfedge *) NULL;
  35.   ELleftend->ELright = ELrightend;
  36.   ELrightend->ELleft = ELleftend;
  37.   ELrightend->ELright = (struct Halfedge *) NULL;
  38.  
  39.   ELhash[0] = ELleftend;
  40.   ELhash[ELhashsize - 1] = ELrightend;
  41. }
  42.  
  43.  
  44. struct Halfedge *
  45. HEcreate (e, pm)
  46.      struct Edge *e;
  47.      int pm;
  48. {
  49.   struct Halfedge *answer;
  50.  
  51.   answer = (struct Halfedge *) getfree (&hfl);
  52.  
  53.   answer->ELedge = e;
  54.   answer->ELpm = (char) pm;
  55.   answer->PQnext = (struct Halfedge *) NULL;
  56.   answer->vertex = (struct Site *) NULL;
  57.   answer->ELrefcnt = 0;
  58.  
  59.   return (answer);
  60. }
  61.  
  62.  
  63. void
  64. ELinsert (lb, new)
  65.      struct Halfedge *lb, *new;
  66. {
  67.   new->ELleft = lb;
  68.   new->ELright = lb->ELright;
  69.   (lb->ELright)->ELleft = new;
  70.   lb->ELright = new;
  71. }
  72.  
  73. /* Get entry from hash table, pruning any deleted nodes */
  74. struct Halfedge *
  75. ELgethash (b)
  76.      int b;
  77. {
  78.   struct Halfedge *he;
  79.  
  80.   if (b < 0 || b >= ELhashsize)
  81.     return ((struct Halfedge *) NULL);
  82.  
  83.   he = ELhash[b];
  84.   if ((he == (struct Halfedge *) NULL) ||
  85.       (he->ELedge != (struct Edge *) DELETED))
  86.     return (he);
  87.  
  88. /* Hash table points to deleted half edge.  Patch as necessary. */
  89.   ELhash[b] = (struct Halfedge *) NULL;
  90.   if ((he->ELrefcnt -= 1) == 0)
  91.     makefree ((struct Freenode *) he, &hfl);
  92.   return ((struct Halfedge *) NULL);
  93. }
  94.  
  95. struct Halfedge *
  96. ELleftbnd (p)
  97.      struct Point *p;
  98. {
  99.   int i, bucket;
  100.   struct Halfedge *he;
  101.  
  102. /* Use hash table to get close to desired halfedge */
  103.   bucket = (int) (((p->x - xmin) / deltax) * ELhashsize);
  104.  
  105.   if (bucket < 0)
  106.     bucket = 0;
  107.   if (bucket >= ELhashsize)
  108.     bucket = ELhashsize - 1;
  109.   he = ELgethash (bucket);
  110.   if (he == (struct Halfedge *) NULL) {
  111.     for (i = 1; 1; i += 1) {
  112.       if ((he = ELgethash (bucket - i)) != (struct Halfedge *) NULL)
  113.         break;
  114.       if ((he = ELgethash (bucket + i)) != (struct Halfedge *) NULL)
  115.         break;
  116.     }
  117.     totalsearch += i;
  118.   }
  119.   ntry += 1;
  120.  
  121. /* Now search linear list of halfedges for the corect one */
  122.   if (he == ELleftend || (he != ELrightend && right_of (he, p))) {
  123.     do {
  124.       he = he->ELright;
  125.     } while (he != ELrightend && right_of (he, p));
  126.     he = he->ELleft;
  127.   }
  128.   else
  129.     do {
  130.       he = he->ELleft;
  131.     } while (he != ELleftend && !right_of (he, p));
  132.  
  133. /* Update hash table and reference counts */
  134.   if (bucket > 0 && bucket < ELhashsize - 1) {
  135.     if (ELhash[bucket] != (struct Halfedge *) NULL)
  136.       ELhash[bucket]->ELrefcnt -= 1;
  137.     ELhash[bucket] = he;
  138.     ELhash[bucket]->ELrefcnt += 1;
  139.   }
  140.   return (he);
  141. }
  142.  
  143.  
  144. /* 
  145.  * This delete routine can't reclaim node, since pointers from hash
  146.  * table may be present.   
  147.  */
  148. void
  149. ELdelete (he)
  150.      struct Halfedge *he;
  151. {
  152.   (he->ELleft)->ELright = he->ELright;
  153.   (he->ELright)->ELleft = he->ELleft;
  154.   he->ELedge = (struct Edge *) DELETED;
  155. }
  156.  
  157.  
  158. struct Halfedge *
  159. ELright (he)
  160.      struct Halfedge *he;
  161. {
  162.   return (he->ELright);
  163. }
  164.  
  165. struct Halfedge *
  166. ELleft (he)
  167.      struct Halfedge *he;
  168. {
  169.   return (he->ELleft);
  170. }
  171.  
  172.  
  173. struct Site *
  174. leftreg (he)
  175.      struct Halfedge *he;
  176. {
  177.   if (he->ELedge == (struct Edge *) NULL)
  178.     return (bottomsite);
  179.   return (he->ELpm == le ? he->ELedge->reg[le] : he->ELedge->reg[re]);
  180. }
  181.  
  182. struct Site *
  183. rightreg (he)
  184.      struct Halfedge *he;
  185. {
  186.   if (he->ELedge == (struct Edge *) NULL)
  187.     return (bottomsite);
  188.   return (he->ELpm == le ? he->ELedge->reg[re] : he->ELedge->reg[le]);
  189. }
  190.